import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-12-19
 * Time: 11:27
 */
public class test2 {
    /*
    LeetCode 215  数组中的第K个最大元素
     */


    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }

    public int qsort(int[] nums,int l,int r,int k){
        if(l==r){
            return nums[l];
        }
        int right = r+1;
        int left = l-1;
        int i=l;
        int key = nums[new Random().nextInt(r-l+1)+l];
        while(i<right){
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else {
                swap(nums,--right,i);
            }
        }

        int b = right-left-1;
        int c = r-right+1;
        if(c>=k){
            return qsort(nums,right,r,k);
        }else if(b+c>=k){
            return key;
        }else{
            return qsort(nums,l,left,k-b-c);
        }
    }

    public void swap(int[] nums,int left,int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = nums[left];
    }
}
